'''
@Author: shj
@Date: 2020-05-30 17:57:16
@LastEditTime: 2020-06-03 09:51:31
@LastEditors: shj
@Description:  二维数组中的查找
@FilePath: /python3/algorithms/offer_code/1_search_in_2d_array.py
'''
'''
题目描述：（查找，数组）
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
'''
"""
解题思路：
注意：二维数组为有序数组（行、列均有序）
先判空，然后二分查找
1）设初始值：定义一个二分的开始下标为l，结束下标为r
2）二分一半，中间位置为 mid = l + （（r - l) >> 1)， 这样的写法是防止溢出。如果写成 mid = （l+r)/2; l+r可能会溢出。
3) 如果 tar == arr[mid]，说明找到tar
4）比较：如果tar > arr[mid], 说明tar在区间[mid+1, r]中，l = mid + 1
5）如果tar < arr[mid]，说明tar在区间[l, mid-1]中, r = mid - 1 
以右上角为例，左下角同理：（arr = [[6]*4] 即4行6列）
1）设初始值为右上角元素，arr[0][5] = val，目标tar = arr[3][1]
2）接下来进行二分操作：
3）如果val == target,直接返回
4）如果 tar > val, 说明target在更大的位置，val左边的元素显然都是 < val，间接 < tar，说明第 0 行都是无效的，所以val下移到arr[1][5]
5）如果 tar < val, 说明target在更小的位置，val下边的元素显然都是 > val，间接 > tar，说明第 5 列都是无效的，所以val左移到arr[0][4]
6）继续步骤2）

    复杂度分析
    时间复杂度：O(m+n) ，其中m为行数，n为列数，最坏情况下，需要遍历m+n次。
    空间复杂度：O(1) 
"""


class Solution(object):
    '''二分查找二维有序数组'''
    def Find(self, target, array):
        '''
        :param target: 目标值
        :param array: 二维有序数组
        '''
        rows = len(array)  # 行数
        clos = len(array[0])  # 列数
        # 判空
        if rows == 0 or clos == 0:
            return 0
        # 右上
        for i in range(rows):
            if array[i][0] <= target <= array[i][-1]:
                l = 0
                r = clos - 1
                while (l <= r):
                    mid = l + (r - l) // 2
                    if array[i][mid] < target:
                        l = mid + 1
                    elif array[i][mid] > target:
                        r = mid - 1
                    else:
                        return True
        return False


# 测试用例
(t, a) = (7, [[1, 2, 8, 9], [2, 4, 9, 12], [4, 7, 10, 13], [6, 8, 11, 15]])

# 结果
sl = Solution()
print(sl.Find(t, a))